#ifndef __SKIP_LIST_H__
#define __SKIP_LIST_H__
#include "Common.h"
#include "Exception.h"
#include "Object.h"
#include "DynamicArray.h"

NAME_SPACE_BEGIN
using u32 = unsigned int;
using u64 = unsigned long long;

class Random {
public:
	explicit Random(u32 s) : m_seed(s & 0x7fffffffu) {
		if (m_seed == 0 || m_seed == 2147483647L)
		{
			m_seed = 1;
		}
	}

	unsigned int Next() {
		static const u32 M = 2147483647L; // 2^31-1
		static const u64 A = 16807;       // bits 14, 8, 7, 5, 2, 1, 0

		u64 product = m_seed * A;		//seed_ = (seed_ * A) % M

		m_seed = static_cast<u32>((product >> 31) + (product & M));

		if (m_seed > M)
		{
			m_seed -= M;
		}

		return m_seed;
	}

	u32 Uniform(int n) { return Next() % n; }

	bool OneIn(int n) { return (Next() % n) == 0; }

	u32 Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); }
private:
	unsigned int m_seed;
};


const int MaxHeight = 12;
template<typename Key, typename Comparator>
class SkipList
{
protected:
	struct Node : public Object {
		explicit Node(const Key& k, const int height) : 
			key(k),
			next_(height)
		{}

		Node* Next(int n) {
			if (n < 0)
			{
				THROW_EXCEPTION(IndexOutOfBoundsException, "Index of i is valid");
			}
			return next_[n];
		}
		
		void SetNext(int n, Node* x) {
			if (n < 0)
			{
				THROW_EXCEPTION(IndexOutOfBoundsException, "Index of i is valid");
			}
			
			next_.set(n, x);
		}

		Key const key;
		DynamicArray<Node*> next_;
	};

public:
	explicit SkipList(Comparator cmp) :
		m_compare(cmp),	
		m_maxHeight(1),
		m_rnd(0xdeadbeef)
	{
		m_header = NewNode(0, MaxHeight);


		for (int i = 0; i < MaxHeight; ++i)
		{
			m_header->SetNext(i, nullptr);
		}
	}

	Node* NewNode(const Key& key, int height) {
		return new Node(key, height);
	}

	void insert(const Key& key) {
		Node* prev[MaxHeight] = {nullptr};
		Node* x = FindGreaterOrEqual(key, prev);

		int height = RandomHeight();
		if (height > GetMaxHeight())
		{
			for (int i = GetMaxHeight(); i < height; ++i)
			{
				prev[i] = m_header;
			}

			m_maxHeight = height;
		}

		x = NewNode(key, height);
		for (int i = 0; i < height; ++i)
		{
			x->SetNext(i, prev[i]->Next(i));
			prev[i]->SetNext(i, x);
		}
	}

	bool Contains(const Key& key) const {
		Node* x = FindGreaterOrEqual(key, nullptr);
		if (x != nullptr && Equal(key, x->key))
		{
			return true;
		}
		else {
			return false;
		}
	}

	int  GetMaxHeight() const {
		return m_maxHeight;
	}

	bool get(const Key& key, Node*& node) {
		Node* x = FindGreaterOrEqual(key, nullptr);
		if (x != nullptr && Equal(key, x->key))
		{
			node = x;
			return true;
		}
		else {
			node = nullptr;
			return false;
		}
	}

private:
	int RandomHeight() {		// 0.25
		static const unsigned int kBranching = 4;
		int height = 1;
		while (height < MaxHeight && ((m_rnd.Next() % kBranching) == 0)) {
			height++;
		}

		if (height > 0 && height <= MaxHeight)
		{
			return height;
		}
		else {
			return 1;
		}
	}

	Node* FindGreaterOrEqual(const Key& key,
		Node** prev) const {

		Node* x = m_header;
		int level = GetMaxHeight() - 1;

		while (true) {
			Node* next = x->Next(level);
			if (KeyIsAfterNode(key, next)) {
				x = next;
			}
			else {
				if (prev != nullptr) {
					prev[level] = x;
				}

				if (level == 0) {
					return next;
				}
				else {
					level--;
				}
			}
		}

		return nullptr;
	}

	bool KeyIsAfterNode(const Key& key, Node* n) const {
		return n != nullptr && (m_compare(n->key, key) < 0);
	}

	bool Equal(const Key& a, const Key& b) const {
		return (m_compare(a, b) == 0);
	}
	

public:
	Comparator m_compare;

	Node* m_header;

	int m_maxHeight;
	Random m_rnd;
};


NAME_SPACE_END

#endif
